package com.example.algorithm.LinkedListAlgorithm;

/**
 * 判断单向链表是否又环. --环路问题--快慢指针
 * @author ZMJ
 * @date 2020/3/23
 */
public class LinkedHaveRingByFastSlow {


/*
快指针走两格，慢指针走1格，若有环，则一定会相遇。
简单理解：
一定是快指针先进入环中，若慢指针也进入环中，则两者速度差1。
相当于慢指针不动（相对静止），而快指针以速度为1，追赶慢指针，（是环，一定会遇到）
若没有环，则快指针将会先到达尾部。
时间复杂度O(n)，空间复杂度O(1)

这个只是解决环路问题一种空间复杂度比较好的方法，
还有简单可以想到的方法--集合思想，将遍历过的数字放入set集合中，
    在放时判断集合是否含有，若含有，则说明有环；若遍历结束，则说明没有环。
 */

    public static boolean isHaveRing(Node head) {
        //当链表没有元素或者只有一个元素（且没环）
        if (head == null || head.getNext() == null) {
            return false;
        }
        Node fast = head;
        Node slow = head;
        /*
          Q1:为什么对slow判断是否为空呢？
          答：因为若没环，fast先到底，while能判断结束
              若有环，则永远不会为空
          Q2:fast.next!=null 为啥加这个
            答：因为在循环内有fast=fast.next.next;
            若fast.next==null，则执行此句会报错
        */
        while (fast != null && fast.getNext() != null) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }


}
